package company.tree;

import java.util.*;

/**
 * 题目如下：
 * 随机给定一棵树，求树中总共的节点个数
 * <p>
 * 思路：
 * （1）定义一个计数器和一个队列（先进先出）
 * （2）先将树的根节点放入队列中，下面执行循环，当队列不为空时，循环一直执行
 * （3）在循环体当中，首先取出队列中的元素，再让result++，后面判断该节点是否有左子节点，如果有就让左子节点入队列；再判断该节点是否有右子节点，如果有们就让右子节点入队列；
 * （4）当队列不为空时，一直执行循环，树的节点都会放入到队列当中，而每一次循环都会在队列中取出一个数据并让result++；
 * （5）直到循环结束，result表示曾经进入到队列的数据个数，即树的节点个数。
 * 注：
 * 当所有节点都入队列之后，循环体当中起作用的功能其实只有取出一个队列中的数据再让result++。
 * <p>
 * 代码如下：
 */
public class Tree {
    TreeNode root;
    Map<Integer, TreeNode> map = new HashMap<>();

    public static void main(String[] args) {
        // 根据 父子节点关系构建树
        Tree tree = new Tree();
        tree.insertOrdinaryTree(6, 3);
        tree.insertOrdinaryTree(3, 9);
        tree.insertOrdinaryTree(3, 7);
        tree.insertOrdinaryTree(6, 1);
        tree.insertOrdinaryTree(1, 4);
        tree.insertOrdinaryTree(7, 5);
        tree.deleteTreeNode(tree.root, 7);
        System.out.println();
    }


    // 普通树
    public void insertOrdinaryTree(int parentid, int value) {
        if (Objects.isNull(root)) {
            root = new TreeNode(parentid);
            TreeNode newNode1 = new TreeNode(value);
            root.setLeft(newNode1);
            map.put(parentid, root);
            map.put(value, newNode1);
            return;
        }
        TreeNode treeNode = map.get(parentid);
        TreeNode newNode = new TreeNode(value);
        if (treeNode.getLeft() == null) {
            treeNode.setLeft(newNode);
        } else if (treeNode.getRight() == null) {
            treeNode.setRight(newNode);
        }
        map.put(value, newNode);
    }

    // 树的构建
    public TreeNode packTree(TreeNode treeNode, String[] node) {
        // 根节点
        if (treeNode == null) {
            treeNode = new TreeNode(Integer.parseInt(node[0]));
        }
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(treeNode);
        int idx = 0;
        int len = node.length;
        while (++idx < len) {
            // 取出父节点
            TreeNode poll = deque.poll();

            // 处理左子树
            if (poll.getLeft() == null) {
                if (!node[idx].equals("null")) {
                    TreeNode left = new TreeNode(Integer.parseInt(node[idx]));
                    poll.setLeft(left);
                    deque.offer(left);
                }
            }
            ++idx;

            // 处理右子树
            if (idx < len && poll.getRight() == null) {
                if (!node[idx].equals("null")) {
                    TreeNode right = new TreeNode(Integer.parseInt(node[idx]));
                    poll.setRight(right);
                    deque.offer(right);
                }
            }
        }
        return treeNode;
    }

    //先序遍历
    public void beforeOrder(TreeNode treeNode) {
        if (treeNode == null) {
            return;
        }
        System.out.print(treeNode.getValue() + " ");
        beforeOrder(treeNode.getLeft());
        beforeOrder(treeNode.getRight());
    }

    //中序遍历
    public void inOrder(TreeNode treeNode) {
        if (treeNode == null) {
            return;
        }
        inOrder(treeNode.getLeft());
        System.out.print(treeNode.getValue() + " ");
        inOrder(treeNode.getRight());
    }

    //后序遍历
    public void afterOrder(TreeNode treeNode) {
        if (treeNode == null) {
            return;
        }
        afterOrder(treeNode.getLeft());
        afterOrder(treeNode.getRight());
        System.out.print(treeNode.getValue() + " ");
    }

    // 层序遍历
    public List<List<Integer>> levelPrint(TreeNode treeNode) {
        if (treeNode == null) {
            return new ArrayList<>();
        }
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(treeNode);

        List<List<Integer>> result = new ArrayList<>();
        while (!deque.isEmpty()) {
            int size = deque.size();
            List<Integer> path = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode poll = deque.poll();
                path.add(poll.getValue());
                TreeNode left = poll.getLeft();
                TreeNode right = poll.getRight();

                if (null != left) {
                    deque.offer(poll.getLeft());
                }
                if (right != null) {
                    deque.offer(poll.getRight());
                }
            }
            result.add(path);
        }
        return result;
    }

    // 统计节点数
    public int countTreeNodeNum(TreeNode treeNode) {
        int count = 0;
        if (treeNode == null) {
            return count;
        }
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(treeNode);
        while (!deque.isEmpty()) {
            TreeNode poll = deque.poll();
            count++;
            TreeNode left = poll.getLeft();
            TreeNode right = poll.getRight();
            if (null != left) {
                deque.offer(poll.getLeft());
            }
            if (right != null) {
                deque.offer(poll.getRight());
            }
        }
        return count;
    }

    // 统计层级
    public int countTreeLevel(TreeNode treeNode) {
        int count = 0;
        if (treeNode == null) {
            return 0;
        }
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(treeNode);

        while (!deque.isEmpty()) {
            int size = deque.size();
            for (int i = 0; i < size; i++) {
                TreeNode poll = deque.poll();
                TreeNode left = poll.getLeft();
                TreeNode right = poll.getRight();

                if (null != left) {
                    deque.offer(poll.getLeft());
                }
                if (right != null) {
                    deque.offer(poll.getRight());
                }
            }
            count++;
        }
        return count;
    }

    // 删除普通2叉树的指定节点以及它的子节点
    public void deleteTreeNode(TreeNode treeNode, int value) {
        if (treeNode == null) {
            return;
        }

        // 找指定节点
        TreeNode parentNode = searParentNode(value, treeNode);

        // 删除指定节点以及子节点
        delNode(parentNode, value);
        System.out.println();
    }

    /**
     * 删除指定节点以及子节点
     *
     * @param node  指定节点的父节点
     * @param value 指定的节点
     */
    private static void delNode(TreeNode node, int value) {
        Deque<TreeNode> deque = new LinkedList<>();
        TreeNode left = node.getLeft();
        TreeNode right = node.getRight();

        // 将删除节点入队列
        if (left.getValue() == value) {
            deque.offer(left);
            node.setLeft(null);
        }
        if (right.getValue() == value) {
            deque.offer(right);
            node.setRight(null);
        }
        while (!deque.isEmpty()) {
            TreeNode poll = deque.poll();
            left = poll.getLeft();
            right = poll.getRight();

            if (left != null) {
                deque.offer(left);
                poll.setLeft(null);
            }
            if (right != null) {
                deque.offer(right);
                poll.setRight(null);
            }
        }
    }

    public TreeNode searParentNode(int value, TreeNode treeNode) {
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(treeNode);
        while (!deque.isEmpty()) {
            TreeNode poll = deque.poll();
            TreeNode left = poll.getLeft();
            TreeNode right = poll.getRight();

            if (left.getValue() == value || right.getValue() == value) {
                return poll;
            }
            if (null != left) {
                deque.offer(poll.getLeft());
            }
            if (right != null) {
                deque.offer(poll.getRight());
            }
        }
        return null;
    }


    //编写前序找指定节点
    public boolean preSearch(TreeNode treeNode, int value) {
        if (null == treeNode) {
            return false;
        }
        //先判断当前节点是否符合
        if (treeNode.getValue() == value) {
            return true;
        }
        //向左递归
        boolean b = preSearch(treeNode.getLeft(), value);
        //向右递归(判断左递归得到的节点是否为空，如果为空，则进行右递归)
        if (!b) {
            b = preSearch(treeNode.getRight(), value);
        }
        return b;//如果最终还是没有找到，则返回null
    }


    //编写中序查找指定节点
    public boolean inSearch(TreeNode treeNode, int value) {
        if (null == treeNode) {
            return false;
        }
        //向左递归
        boolean b = inSearch(treeNode.getLeft(), value);

        // 中节点
        if (!b) {
            if (treeNode.getValue() == value) {
                return true;
            }
        }

        //向右递归(判断左递归得到的节点是否为空，如果为空，则进行右递归)
        if (!b) {
            b = inSearch(treeNode.getRight(), value);
        }
        return b;//如果最终还是没有找到，则返回null
    }

    //编写后序查找指定节点
    public boolean afterSearch(TreeNode treeNode, int value) {
        if (null == treeNode) {
            return false;
        }
        //向左递归
        boolean b = afterSearch(treeNode.getLeft(), value);

        //向右递归(判断左递归得到的节点是否为空，如果为空，则进行右递归)
        if (!b) {
            b = inSearch(treeNode.getRight(), value);
        }

        // 中节点
        if (!b) {
            if (treeNode.getValue() == value) {
                return true;
            }
        }
        return b;//如果最终还是没有找到，则返回null
    }
}